package q167_twoSum;

public class Solution_3 {
    /*
    二分查找解法
    可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。
    利用数组的有序性质，可以通过二分查找的方法寻找第二个数。
    为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找

    但是本质上还是时间复杂度达到nlogn
     */
    public int[] twoSum(int[] numbers, int target) {
        // 外部循环
        for (int i = 0; i < numbers.length; ++i) {
            // 这里利用low和high来固定一个数 然后利用数组有序来二分查找是否有对应的target - n[i]
            int low = i + 1, high = numbers.length - 1;
            // 内部循环
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};

    }
}
